package fag.core.collision;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

import fag.core.geometry.Rectangle2D;
import fag.core.geometry.Vector2D;

/**
 * Classe de partitionnement d'espace grâce à un arbre quaternaire.
 * @author lumz
 */
public class Quadtree {
	
	/**
	 * Classe quadrant de l'arbre quaternaire.
	 * @author lumz
	 */
	public static class Quadrant implements Iterable<Hitbox> {

		private Quadtree quadtree = null;
		private List<Quadrant> children = new ArrayList<Quadrant>();
		private int depth = 0;
	
		private Rectangle2D bounds = null;
		private List<Hitbox> hitboxes = new ArrayList<Hitbox>();
		
		/**
		 * Constructeur par défault.
		 * @param depth Profondeur de ce quadrant depuis la racine.
		 */
		private Quadrant(Quadtree quadtree, int depth) {
			this.quadtree = quadtree;
			this.depth = depth;
		};
		
		/**
		 * Implémentation de Iterable<Hitbox>. Permet d'itérer sur les objets contenus dans un quadrant.
		 * @return L'itérateur de ce quadrant.
		 */
		public Iterator<Hitbox> iterator() {
			return new Iterator<Hitbox>() {
				
				private int index = 0;

				/**
				 * Vérifier qu'il existe un successeur.
				 */
				public boolean hasNext() {
					return index < hitboxes.size();
				}

				/**
				 * Obtenir le successeur.
				 * @return Le successeur.
				 */
				public Hitbox next() {
					
					if(!hasNext())
						throw new NoSuchElementException();
					
					Hitbox next = hitboxes.get(index);
					++index;
					
					return next;
				}

				/**
				 * Méthode non disponible.
				 */
				public void remove() {
					throw new UnsupportedOperationException();
				}
			};
		}
		
		/**
		 * Ajouter une boîte de collision à ce quadrant.
		 * @param item boîte de collision à ajouter.
		 */
		private void add(Hitbox item) {
			
			hitboxes.add(item);
			
			// Limiter la profondeur de l'arbre
			if(depth <= quadtree.getMaxDepth()) {
				
				// Si le poid devient trop grand alors prévoir des quadrants fils
				if(hitboxes.size() > quadtree.getMaxWeight() && children.size() == 0)
					grow();
				
				// Il ne s'agit pas d'une feuille distribuer les objets dans les quadrants fils
				if(children.size() != 0)
					split();
			}
		}
		
		/**
		 * Regroupe l'ensemble des feuilles qui contiennent des objets et qui se trouvent sur cette branche.
		 * @return L'ensemble des feuilles qui se trouvent sur cette branche.
		 */
		private List<Quadrant> getPopulatedLeavesOnBranch() {
			
			List<Quadrant> result = new ArrayList<Quadrant>();
			
			// Récursion
			if(children.size() != 0)
				for(Quadrant child : children)
					result.addAll(child.getPopulatedLeavesOnBranch());
				
			// Ajouter si cette feuille contient des objets
			if(hitboxes.size() != 0)
				result.add(this);
			
			return result;
		}
		
		/**
		 * Ajouter quatre quadrants fils.
		 */
		private void grow() {
			
			// Création des fils
			for(int i = 0; i < 4; ++i) {
				
				Quadrant child = new Quadrant(quadtree, depth + 1);
				
				child.bounds = new Rectangle2D(bounds.getX() + bounds.getWidth() / 2 * (i % 2),
						bounds.getY() + bounds.getHeight() / 2 * (i / 2),
						bounds.getWidth() / 2,
						bounds.getHeight() / 2);
				
				children.add(child);
			}
		}
		
		/**
		 * Distribuer les objets du quadrant dans ses quadrants fils.
		 */
		private void split() {
			
			// Distribution des objet dans les fils nouvellement crée
			Vector2D center = new Vector2D(bounds.getX() + bounds.getWidth() / 2, bounds.getY() + bounds.getHeight() / 2);
			
			Iterator<Hitbox> it = hitboxes.iterator();
			while(it.hasNext()) {
				
				Hitbox hitbox = it.next();
				Rectangle2D bounds = hitbox.getBounds();
				
				// Noeuds gauches
				if(bounds.getX() < center.x) {
					
					// NW
					if(bounds.getY() < center.y) {
						children.get(0).add(hitbox);
					}
					
					// NE
					if(bounds.getY() + bounds.getHeight() >= center.y) {
						children.get(2).add(hitbox);
					}
				}
	
				// Noeuds droits
				if(bounds.getX() + bounds.getWidth() >= center.x) {
					
					// NE
					if(bounds.getY() < center.y) {
						children.get(1).add(hitbox);
					}
					
					// SE
					if(bounds.getY() + bounds.getHeight() >= center.y) {
						children.get(3).add(hitbox);
					}
				}
			}
			
			// Retirer du quadrant
			hitboxes.clear();
		}
	}
	
	private final static int DEFAULT_MAX_WEIGHT = 3;
	private final static int DEFAULT_MAX_DEPTH = 3;
	
	private Rectangle2D bounds = null;
	
	private int maxWeight = 4;
	private int maxDepth = 4;
	
	private Quadrant root = new Quadrant(this, 0);
	
	/**
	 * Constructeur par défaut.
	 * @param bounds Bornes de l'arbre quaternaire.
	 */
	public Quadtree(Rectangle2D bounds) {
		this.bounds = bounds.clone();
		this.maxWeight = DEFAULT_MAX_WEIGHT;
		this.maxDepth = DEFAULT_MAX_DEPTH;
	}
	
	/**
	 * Constructeur avec spécification du poids maximal et de la profondeur maximale.
	 * @param bounds Bornes de l'arbre quaternaire.
	 * @param maxWeight Poid maximal d'une feuille de l'arbre.
	 */
	public Quadtree(Rectangle2D bounds, int maxWeight, int maxDepth) {
		this.bounds = bounds.clone();
		this.maxWeight = maxWeight;
		this.maxDepth = maxDepth;
	}
	
	/**
	 * Accesseur des feuilles de l'arbre quaternaire qui contiennent des objets.
	 * Regroupe les objets par régions.
	 * @return Une liste des régions qui contiennent des groupes d'objets.
	 */
	public List<Quadrant> getPopulatedLeaves() {
		return root.getPopulatedLeavesOnBranch();
	}
	
	/**
	 * Accesseur de la pronfondeur maximale de l'arbre.
	 * @return La profondeur maximale de l'arbre.
	 */
	public int getMaxDepth() {
		return maxDepth;
	}
	
	/**
	 * Accesseur du poids maximal d'une feuille de l'arbre.
	 * @return Le poids maximal d'une feuille de l'arbre.
	 */
	public int getMaxWeight() {
		return maxWeight;
	}
	
	/**
	 * Construire l'arbre quaternaire.
	 * @param items Les objets à répartir.
	 */
	public void build(List<? extends Hitbox> items) {
		
		root = new Quadrant(this, 0);
		root.bounds = bounds;
		
		int size = items.size();
		for(int i = 0; i < size; ++i) {
			root.add(items.get(i));
		}
		
		// Affecter les quadrants des boîtes de collisions
		List<Quadrant> quadrants = getPopulatedLeaves();
		for(int i = 0; i < quadrants.size(); ++i) {
			
			Quadrant quadrant = quadrants.get(i);
			
			for(Hitbox hitbox : quadrant)
				hitbox.quadrant = quadrant;
		}
	}
	
	/**
	 * Accesseur de la pronfondeur maximale de l'arbre.
	 */
	public void setMaxDepth(int maxDepth) {
		this.maxDepth = maxDepth;
	}
	
	/**
	 * Accesseur du poids maximal des feuilles de l'arbre.
	 */
	public void setMaxWeight(int maxWeight) {
		this.maxWeight = maxWeight;
	}
}
